import java.util.*;

public class MapSetTest2 {
    public static List<String>  topKfrequent(String[] words, int k) {
        //1. 遍历数组,统计每个单词出现的频率
        Map<String,Integer> hashMap = new HashMap<>();
        for (String s: words) {
            if(hashMap.get(s) == null){
                hashMap.put(s,1);
            }else{
                int value = hashMap.get(s);
                hashMap.put(s,value+1);
            }
        }
        //2. 建立小根堆,前k个
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(
                k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //3. 遍历hashMap 把 里面的 数据 放到小根堆
        for (Map.Entry<String,Integer> entry:hashMap.entrySet()) {
            if(minHeap.size() < k){//没有放满
                minHeap.offer(entry);
            }else {//小根堆 放满了k个,下一个 entry 和 堆顶元素比较
                Map.Entry<String,Integer> top =  minHeap.peek();
                //堆顶的频率小于当前 entry的频率 就出队, 入队 entry
                if(top.getValue().compareTo(entry.getValue()) <0){
                    minHeap.poll();
                    minHeap.add(entry);
                }else {
                    //频率相同
                    if(top.getValue().compareTo(entry.getValue()) == 0){
                        //比较key值
                        if(top.getKey().compareTo(entry.getKey()) >0){
                            minHeap.poll();
                            minHeap.add(entry);
                        }
                    }
                }
            }
        }
        //4. 此时,小根堆当中已经有了结果
       // System.out.print(minHeap);
        List<String> ret = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            String key = minHeap.poll().getKey();
            ret.add(key);
        }
        Collections.reverse(ret);
        //System.out.println(ret);
        return ret;
    }
    public static void main(String[] args) {
        String[] words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
       List<String> ret =  topKfrequent(words,4);
        System.out.println(ret);
    }
}
